// 给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。 

// 如果没有两个连续的 1，返回 0 。

// 示例 1：

// 输入：22
// 输出：2
// 解释：
// 22 的二进制是 0b10110 。
// 在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
// 第一对连续的 1 中，两个 1 之间的距离为 2 。
// 第二对连续的 1 中，两个 1 之间的距离为 1 。
// 答案取两个距离之中最大的，也就是 2 。

// 示例 2：

// 输入：5
// 输出：2
// 解释：
// 5 的二进制是 0b101 。

// 示例 3：

// 输入：6
// 输出：1
// 解释：
// 6 的二进制是 0b110 。

// 示例 4：

// 输入：8
// 输出：0
// 解释：
// 8 的二进制是 0b1000 。
// 在 8 的二进制表示中没有连续的 1，所以返回 0 。

// 提示：

// 	1 <= N <= 10^9

#include <vector>

using namespace std;

class Solution1 {
public:
    int binaryGap(int N) {
        vector<int> pos{};
        for (int i = 0; i < 32; ++i) {
            if (((N >> i) & 1) != 0) pos.push_back(i);
        }
        int res{0};
        int n = pos.size();
        for (int i = 1; i < n; ++i) {
            res = max(res, pos[i] - pos[i-1]);
        }
        return res;
    }
};

class Solution {
public:
    int binaryGap(int N) {
        int res{0};
        int last{-1};
        for (int i = 0; i < 32; ++i) {
            if (((N >> i) & 1) != 0) {
                if (last >= 0) res = max(res, i - last);
                last = i;
            }
        }
        return res;
    }
};

class Solution {
public:
    int binaryGap(int n) {
        int res = 0;
        int last_index = -1;
        for (int i = 0 ; i < 32; ++i) {
            if (n & (1 << i)) {
                if (last_index != -1) {
                    res = max(res, i - last_index);
                }
                last_index = i;
            }
        }
        return res;
    }
};
